AKS 素数判定法
$ d桁の数の素数判定を行うために$ \tilde\Omicron(d^{7.5})かかる いずれにせよ実用的な範囲ではない
実用的なアルゴリズムは$ \Omicron(n^2)以下であることが多く$ \Omicron(n^3)になると遅いと言われる。 $ \rm P\sube PRIME\text-like\sube NP
実際は AKS 素数判定法により $ \rm PRIME\in Pであることが示されたため、 $ \rm P=PRIME\text-like\sube NP
となり、階層$ \rm PRIME\text-likeは$ \rm Pに吸収されて崩壊した。
関数
$ {\rm order}_r(n):=\min\{x\ |\ n^x\overset r\equiv1\}
正の自然数$ n\in\N^+に対して$ nと互いに素である自然数$ m\quad(1\le m<n)の個数を$ \phi(n)とする。 多項式環
体$ K上の多項式環を$ K\lbrack X\rbrackで表す
多値 mod
$ x\equiv y\quad{\rm mod}(a,b)は以下のように判定する
$ x-y=k_1a+k_2b\quad(\exist k_1,k_2\in\Z)
アルゴリズム
$ {\rm Input}(n)\to{\rm Output({Prime}/{Composite})};
$ {\rm Assert}(n\ge2);
1. $ ^{\exist a,b\in\N}\lbrack n=a^b\rbrack\quad\Rightarrow\quad{\rm Retrun({Composite})}\quad
2. $ r:=\min\{r\ |\ {\rm order}_r(n)>4\log^2n\}\in\N
3. $ ^{\exist a\le r}\left\lbrack1<\gcd(a,n)<n\right\rbrack\quad\Rightarrow\quad{\rm Retrun(Composite)}
4. $ \lbrack n\le r\rbrack\quad\Rightarrow\quad{\rm Retrun(Prime)}
5. $ \forall a\in\,_{1\le}\N_{\le2\log n\sqrt{\phi(r)}}
$ (X+a)^n-(X^n+a)\not=k_1(X^r-1)+k_2n\quad\Rightarrow\quad{\rm Return(Composite)}
$ {\rm elihW}
6. $ {\rm Return(Prime)}
メインのステップはステップ 5
それまでの処理は前処理
$ a,nは互いに素であるとする。
$ a\in(\Z/n\Z)^\times
$ a^p\overset p\equiv a\quad p\in\mathbb P
$ x^p\overset p\equiv x
$ (x+a)^p=x^p+\sum_{r=1}^{p-1}\,_pC_rx^ra^{p-r}+a^p
$ \overset p\equiv x^p+a^p$ \quad$ \because$ p\ |\ _pC_r\quad(\forall r\in\N_{\le p-1}^+)
$ \overset p\equiv x^p+a$ \quad$ \because a^p\overset p\equiv a
$ a^{\lambda(n)}\overset n\equiv1\quad(n\in\N)
$ x^{\lambda(n)}\overset n\equiv1
$ \lambda(n)\in\N|(n-1)のとき
$ a^{n-1}=(a^{\lambda(n)})^\bullet\overset n\equiv1^\bullet=1
$ a^n\overset n\equiv a
$ x^n\overset n\equiv x
$ (x+a)^n\overset n\equiv x+a
$ \overset n\equiv x^n+a
カーマイケル数は$ \overset n\equivの部分は通ってしまう。